P4900 食堂

题目需要求的是这个式子:

i=ABj=1i{ij}\sum_{i=A}^B\sum_{j=1}^i \{\frac{i}{j}\}

小学奥数知识可知:{x}=x[x]\{x\}=x-[x]

所以上式等价于:

i=ABj=1i(ij[ij])\sum_{i=A}^B\sum_{j=1}^i(\frac{i}{j}-[\frac{i}{j}])

i=ABj=1iiji=ABj=1i[ij]\sum_{i=A}^B\sum_{j=1}^i\frac{i}{j}-\sum_{i=A}^B\sum_{j=1}^i[\frac{i}{j}]

先看前部分,

i=ABj=1iij\sum_{i=A}^B\sum_{j=1}^i\frac{i}{j}

i=ABij=1iinv[j]\sum_{i=A}^Bi\sum_{j=1}^i inv[j]

递推求出 invinv 数组,做前缀和后与 ii 相乘,记为 firfir

再将 firfir 数组求前缀和后得到第一部分答案。

再看后部分,

i=ABj=1i[ij]\sum_{i=A}^B\sum_{j=1}^i[\frac{i}{j}]

i=ABj=1id(j)\sum_{i=A}^B\sum_{j=1}^id(j)

线性筛出约数个数后求两次前缀和即可。

时间复杂度 Θ(n+t)\Theta(n+t)

#include <cstdio>
#define Mod 998244353

const int MAXN = 1000000;
int t , l , r , k , d[ MAXN + 5 ] , num[ MAXN + 5 ] , prime[ MAXN + 5 ];
int inv[ MAXN + 5 ] , pre_inv[ MAXN + 5 ];
int fir[ MAXN + 5 ] , sec[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
    d[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ k ] = i;
            d[ i ] = 2 , num[ i ] = 1;
        }
        for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) {
                d[ i * prime[ j ] ] = d[ i ] / ( num[ i ] + 1 ) * ( num[ i ] + 2 );
                num[ i * prime[ j ] ] = num[ i ] + 1;
                break;
            }
            d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
            num[ i * prime[ j ] ] = 1;
        }
    }
}
void Init( ) {
    inv[ 0 ] = inv[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ )
        inv[ i ] = 1ll * ( Mod - Mod / i ) * inv[ Mod % i ] % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
       pre_inv[ i ] = ( pre_inv[ i - 1 ] + inv[ i ] ) % Mod;

    for( int i = 1 ; i <= MAXN ; i ++ )
        fir[ i ] = 1ll * i * pre_inv[ i ] % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
        fir[ i ] = ( fir[ i - 1 ] + fir[ i ] ) % Mod;
    
    sieve( );
    for( int i = 1 ; i <= MAXN ; i ++ )
        sec[ i ] = ( sec[ i - 1 ] + d[ i ] ) % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
        sec[ i ] = ( sec[ i - 1 ] + sec[ i ] ) % Mod;
}

int main( ) {
    Init( );
    scanf("%d",&t);
    while( t -- ) {
        scanf("%d %d",&l,&r);
        printf("%d\n", ( ( fir[ r ] - fir[ l - 1 ] + Mod ) % Mod - ( sec[ r ] - sec[ l - 1 ] + Mod ) % Mod + Mod ) % Mod );
    }
    return 0;
}